1. Field of the Invention
The invention relates to a process for the compression of data representative of an image signal, of the type consisting of decomposing the image into blocks forming arrays of pixels, of effecting a mathematical transformation operation on each array of pixels according to a transform that permits obtaining a resulting array of elements representative of the activity of the image, and of eliminating in each resulting array the elements of low psychovisual pertinence by thresholding in relation to an array of reference thresholds.
More specifically, the invention relates to a process of implementation of a new transform of the arrays of pixels, enabling the process of compression to be implemented at low cost.
The invention applies advantageously, but not exclusively, to the compression of images emitted in sequences of images at reduced rate, of the type used in audiovideography, photovideotex, telesurveillance, or in visiophony and visioconference on a switched telephone network, or on a digital network with service integration. However, the invention applies also to any other type of images or of sequences of images, including the coding of digital television pictures and even of high definition television.
2. Description of the Prior Art
Several laws of transformation of arrays of pixels are known, the principal laws being the Fast Fourier Transform, FFT, and the Discrete Cosine Transform, DCT. At least three parameters determine the choice of the transform, for a given application:
the rate of compression of the image signal; PA1 the psychovisual quality of the image reconstituted from the compressed image signal; and PA1 the "processing speed x semiconductor area" cost of implementation of the transform on integrated circuit. PA1 u,v: coordinates of the coefficients of the transformed array, PA1 C(u)=1/.sqroot.2 if u=0, PA1 C(v)=1 if u.noteq.0, and PA1 f(i,j): amplitude of the pixel of coordinates (i,j). PA1 the decomposition of the lines/columns during implementation of the DCT on the array of pixels; and PA1 the implementation of the DCT directly in two dimensions, through a decomposition into elementary steps which in the aggregate is less expensive. PA1 a permutation of the elements of the initial array of pixels; PA1 an FFT generated on the permuted array; and PA1 a series of rotations applied to the array transformed by the FFT, so as to obtain the final array corresponding to the DCT transform of the initial array of pixels.
The DCT is generally the transform prefered today for the compression of images, because it permits a higher concentration of the "activity" ("energy") of the image than the FFT. In other words, the transformed array resulting from the CDT operation on the initial array of pixels, comprises fewer significant elements, from the psychovisual point of view. The amount of information relative to the image is therefore smaller, which permits the transmission of the image signal at a slower rate.
However, the implementation of the CDT on the arrays of pixels implies a "processing speed x semiconductor area" cost greater than that of the FFT. All the recent research of the experts in this area aimed therefore to find means to implement the CDT which minimizes this cost.
The CDT implemented on an image block N.times.N is expressed by the formula: ##EQU1## where: i,j: spatial coordinates of the pixel array elements,
The objective of the weighting coefficients C(u) and C(v) is to take into account the edge effect in the transformed block. The calculation of the double sum, effected systematically, leads to effect N.sup.2 multiplications, multiplied by N.sup.2 coefficients, or N.sup.4 values to be summed.
Now, the cost of implementation of the DCT, on an integrated circuit, is tied directly to the number of additions and multiplications to be done. Further, it should be noted that the cost of a multiplication operation is about 5 to 7 times greater than that of an addition operation.
Two approaches have been tried to reduce the cost of implementation of the transform:
An illustration of the first approach is the method recommended by CHEN and others (see article W. H. CHEN, C. H. SMITH, S. C. FPALICK, "A fast computational algorithm for the Discrete Cosine Transform", IEEE Trans. on Communication, vol. COM-25, Sept. 1977). The method presented consists, essentially, of using the symmetries appearing in the transformation array to reduce the number of operations. The decomposition into lines/columns amounts to effecting successively two series of one dimentional transforms, successively on the lines, and on the columns of the array respectively. The intermediate array, between the two series of transformation, is subjected to a line/column transposition, so that the same mathematical index operations can be applied for the two series of transformations. The approach of CHEN makes it possible to reduce the cost of the DCT to 256 multiplications and 416 additions for arrays of 8.times.8 pixels.
Another method based on the same principle is described in the article of B. C LEE "A new algorithm to compute the discrete cosine Transform" (IEEE trans. ASSP vol. ASSP. 32). This approach is slightly less expensive, in the aggregate, for it requires only 192 multiplications, at the cost of a small increase of the number of additions (464 additions).
Finally, contrary to the preceding methods with direct factorizing, M. VETTERLI and H. NUSSBAUMER have proposed a method by decomposition of the DCT into elementary steps, in "Algorithmes de transformations de Fourier et en Cosinus mono et bidimensionnels" (Algorithms for Fourier and in Cosine one and two-dimensional transformations) (Ann. des Telecom. 40 n0 9-10, 1985). According to this method, the DCT is decomposed into three successive operations, which are:
The FFT on the permuted array is generated in the form of two series of one dimensional transformations, applied successively to the lines of the permuted initial array, then to the columns of the intermediate array resulting from the first series of one dimensional transformations. This method represents a cost of 464 additions, and of 192 multiplications, which can be reduced to 176 multiplications through arithmetical astuteness.
An additional gain has been obtained by VETTERLI, by means of a direct two-dimensional approach, based on the same type of decomposition into three successive operations (see the article "Fast 2-D Discrete Cosine Transform" ICASSP 1985). Contrary to the one dimensional approach, the permutation, FFT and rotation operations are effected directly in two dimensions. The FFT, in particular, is generated by an approach of polynomial transformation of the entire array. The cost of this two-dimensional method is interesting, since it is reduced to 104 multiplications and 460 additions.